Search Results

Documents authored by Lockhart, Joshua


Document
The Computational Complexity of Portal and Other 3D Video Games

Authors: Erik D. Demaine, Joshua Lockhart, and Jayson Lynch

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)


Abstract
We classify the computational complexity of the popular video games Portal and Portal 2. We isolate individual mechanics of the game and prove NP-hardness, PSPACE-completeness, or pseudo-polynomiality depending on the specific game mechanics allowed. One of our proofs generalizes to prove NP-hardness of many other video games such as Half-Life 2, Halo, Doom, Elder Scrolls, Fallout, Grand Theft Auto, Left 4 Dead, Mass Effect, Deus Ex, Metal Gear Solid, and Resident Evil. These results build on the established literature on the complexity of video games [Aloupis et al., 2014][Cormode, 2004][Forisek, 2010][Viglietta, 2014].

Cite as

Erik D. Demaine, Joshua Lockhart, and Jayson Lynch. The Computational Complexity of Portal and Other 3D Video Games. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.FUN.2018.19,
  author =	{Demaine, Erik D. and Lockhart, Joshua and Lynch, Jayson},
  title =	{{The Computational Complexity of Portal and Other 3D Video Games}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{19:1--19:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.19},
  URN =		{urn:nbn:de:0030-drops-88104},
  doi =		{10.4230/LIPIcs.FUN.2018.19},
  annote =	{Keywords: video games, hardness, motion planning, NP, PSPACE}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail